package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         395,
		Discription: "每个字符串至少有k个的最长子串",
		Level:       2,
		Labels: map[string]int{
			"滑动窗口": 1,
			"哈希表":  1,
		},
	})
}

func LongestSubstring(s string, k int) int {
	maxLen := 0
	n := len(s)
	//滑动窗口的内的字符种类数量从1到min(26,len(s))遍历一遍
	for i := 1; i <= 26 && i <= len(s); i++ {
		left := 0
		right := 0
		//滑动窗口内字符串的种类数
		kindNum := 0
		//剩余的个数不足k的字符种类
		unsatisifiedNum := 0
		//滑动窗口内各字符出现的次数
		chCount := make([]int, 26)

		for left <= right && right < n {
			chIndex := int(s[right] - 'a')
			if chCount[chIndex] == 0 {
				kindNum++
				unsatisifiedNum++
			}
			chCount[chIndex]++
			if chCount[chIndex] == k {
				unsatisifiedNum--
			}

			//先保证滑动窗口内的字符串种类数<=当前遍历的种类数
			for kindNum > i {
				removedChIndex := int(s[left] - 'a')
				left++
				if chCount[removedChIndex] == k {
					unsatisifiedNum++
				}
				chCount[removedChIndex]--
				if chCount[removedChIndex] == 0 {
					kindNum--
					unsatisifiedNum--
				}
			}

			//这个必须放在最后
			if unsatisifiedNum == 0 {
				maxLen = max(maxLen, right-left+1)
			}
			right++
		}
	}

	return maxLen
}
